package reviewAlgorithms.search;

import java.util.ArrayList;
import java.util.List;

public class Partition {
    public static void main(String[] args) {
        String s = "aabbb";
        List<List<String>> res = partition(s);
        for (List<String> item : res) {
            System.out.println(item);
        }
    }

    public static List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() < 1){
            return res;
        }
        int end = 0;
        List<String> oneRes = new ArrayList<>();
        getPartition(s,end,res,oneRes);
        return res;
    }

    private static void getPartition(String s, int end, List<List<String>> res, List<String> oneRes) {
        if (end >= s.length()){
            res.add(new ArrayList<>(oneRes));
            return;
        }
        int start = end;
        for (int i = start + 1; i <= s.length(); i++) {
            end = i;
            if (isLegal(s.substring(start,end))){
                oneRes.add(s.substring(start,end));
                getPartition(s,end,res,oneRes);
                oneRes.remove(oneRes.size() - 1);
            }
        }
    }

    private static boolean isLegal(String substring) {
        StringBuilder stringBuilder = new StringBuilder(substring);
        stringBuilder.reverse();
        return stringBuilder.toString().equals(substring);
    }
}
